package prac10;
/* Class LinearProbe<K extends Hashable,D>
 * 
 * Objective: Generic Hash Table data type implemented using linear probe 
 *            techniques
 * 
 * @author Maria Garcia de la Banda
 * @modified Menghong Li
 * 
 * @modified May 2011
 * @since    April 2007
 * @input none
 * @output none
 * @errorHandling   none
 * @knownBugs       none
 */

public class LinearProbe<K extends Hashable,D> {  
    private Entry[] hashTable;
    private int collisions = 0;
    private int probes = 0;
    
    
    
    /**
	 * @return the collisions
	 */
	protected int getCollisions() {
		return collisions;
	}

	/**
	 * @return the probes
	 */
	protected int getProbes() {
		return probes;
	}

	/**
     * invariant: if an Entry is stored in position N, then
     *      N is either the hash value of the Entry's key K, or the first empty 
     *      position from the hash value when Entry was inserted. 
     * invariant (corollary of the above, really): there are
     *      no empty spaces between items with the same hash value.
     */
    private class Entry {  
        K key;
        D data;

        private Entry(K newKey, D newData) {
	    key = newKey; 
	    data = newData;
	} 

        private K getKey() {
	    return key;
	}   

        private D getData() {
	    return data;
	}

        public String toString() {
	    return key + "::"  + data;
	}
    }

    /**
     * Creates a new HashTable: empty array of the given size
     *
     * @param       size of the table
     * @pre         size is positive
     * @post        an empty array of the given size
     * @complexity  best and worst case: O(1) (multiplied by the 
     *              complexity of "new")
     */
    public LinearProbe(int size) {
	hashTable = new LinearProbe.Entry[size]; 
	this.collisions = 0;
	this.probes = 0;
    }                                                                            
    /**
     * Inserts a new element into the hash table. It returns true if the item 
     * is inserted in the first empty slot from the associated hash value, 
     * false if there are no empty slots
     *
     * @pre  the element does not already appear in the table
     * @post if it returns false, hashTable is full and left unchanged. If
     *       it returns true, hashTable has a new element, and all cells from
     *       "position" to where Entry(key,data) is finally added to, are full
     * @complexity 	Best case: O(A)	when the first position tried is empty (i.e., 
     *       		where A is the complexity of hash(),
     *       
     *       		Worst case: O(M)+O(A), 
     */
    public boolean insert(K key, D data) {
	int position = key.hash();
	
	if (hashTable[position] != null) {
        collisions++;
    }
                                                                             
	for (int count = 0; count < hashTable.length; count++) {
	    if (hashTable[position] == null) { // empty cell
	    	hashTable[position] = new Entry(key,data);
	    	return true;
	    } else { // still looking
	    	if(!hashTable[position].getKey().equals(key)){
		    	probes++;
		    	position =(position+1)%hashTable.length;
	    	}
	    }
	}
	return false;
    }
 
    /**
     * Searches for the data associated to a particular key (if any).
     * It returns D if it can find the item, null if it cannot
     *
     * @pre none
     * @post If it returns null, there is no cell in hashTable with 
     *       the chosen key, if it returns D, then a cell with that key exists, 
     *       and has D as data. Also, hashTable is unchanged.
     * @complexity Best case: when D is in the first position (i.e., the length
     *      of the probe is 1): A+B where A is the complexity of hash(), which
     *      is usually  O(M) (where M is the max size of the elements in the 
     *      key), B is the complexity of equals() which is usually O(N) where 
     *      N is the max size of the data (note that the complexity of getKey 
     *      and getData() is O(1))
     * @complexity Worst case: when the table is full and the element is not 
            there: A+O(TABLESIZE)*B+, since the length of the probe is equal to 
     *      the size of the table. Again, average is O(1) if properly 
     *      constructed.
     */
    public D search(K key) {
	int position = key.hash();
	if (hashTable[position] != null) {
		if (!hashTable[position].getKey().equals(key)) {
            collisions++;
        }
    }
                                                    
	for (int count = 0; count < hashTable.length; count++) {
	    if (hashTable[position] == null) {
	    	return null;
	    } else if (key.equals(hashTable[position].getKey())) {
	    	return hashTable[position].getData();
	    } else {
	    	probes++;
	    	position =(position+1)%hashTable.length;
        }
    }
	return null;
    }

    /**
     * Used to print all elements in the hashTable, each in a line
     *
     * @pre none new
     * @post the hashTable is unchanged
     * @complexity Best and worst cases are the same: O(TABLESIZE)*A where 
     *      A is the complexity of the toString method for Entry 
     */
    public void printItems() {
        for (int i=0; i<hashTable.length ; i++) {
	    if (hashTable[i] != null) {
                System.out.println(hashTable[i]);
            }
	}
    }
}
 
